import java.util.Arrays;

/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class JumpGameII {

	public int jump(int[] A) {
		int n = A.length;
		int[] d = new int[n];
		Arrays.fill(d, Integer.MAX_VALUE);
		d[0] = 0;
		int[] q = new int[n];
		int head = 0, rear = -1;
		q[++rear] = 0;
		for (int i = 1; i < n; ++i) {
			while (head <= rear) {
				if (q[head] + A[q[head]] < i)
					head++;
				else {
					d[i] = d[q[head]] + 1;
					break;
				}
			}
			if (i + A[i] > q[rear] + A[q[rear]]) {
				q[++rear] = i;
			}
		}
		return d[n - 1];
	}

	public static void main(String[] args) {
		JumpGameII a = new JumpGameII();
		System.out.println(a.jump(new int[] { 2, 3, 1, 4, 4 }));
	}

}
